题目分析
题目通俗易懂小伙伴们不要害怕困难题,先试一试将自己的想法实现出来。
暴力
暴力法是我们直观想到的一种解决方法,我们既然要比较相似度,就要求交集和并集。因此i和j两层循环,然后在循环中计算交集和并集。
算法的**时间复杂度为$O(nm^2)$,空间复杂度为$O(1)$**,其中n为每个文档的平均长度,m为文档个数。
但是n和m的最大值都是500,因此$nm^2 = 1.25e8$会TLE,因此这个算法无法通过所有的测试样例。
1 | #include<iostream> |
哈希表
我们有一些隐含条件没有用到,就是题目中所说的稀疏文档。对于大部分文档来说,它们之间都是不需要计算的,没有重复元素,或者500个元素中只有很少的几个是相似的,那么我们如何节省运算呢?
**我们可以统计每个元素有哪些文档包含,因为比较稀疏,所以文档包含同一个元素的概率非常低。假如10这个元素出现在文档1,文档5,文档8中,那么我们建立一个哈希表,其中键为10,值为{1, 5, 8}的一个数组。这时我们可知1和5有一个相似的元素,1和8有一个相似的元素,5和8有一个相似的元素。这时再用一个数组intersection记录文档i和文档j的相似元素个数。即intersection[1][5]++,intersection[1][8]++,intersection[5][8]++**。
$$similarity = \frac{intersection[i][j]}{(docs[i].size() + docs[j].size() - intersection[i][j])}$$
其中分子是交集元素个数,分母是并集元素个数。这里用到了一部分数学知识,交集数量+并集数量=两个集合数量之和。
在稀疏文档中,文档包含同一个元素的平均个数为常数量级,算法的**时间复杂度为$O(nm)$,在统计每个元素有哪些文档时,用到m x n的空间,在计算文档之间相似元素个数时,用到m x m的空间。因此空间复杂度为$O(m \times max(m, n))$**,其中n为每个文档的平均长度,m为文档个数。
1 | #include<iostream> |
刷题总结
哈希表典型的特征是以空间换时间,我们有了哈希表,可以用额外的空间去存储数据的属性,以后查找的时候就不需要遍历数组。哈希表的题目,小伙伴要多多练习。